package part_1;

import genetic_algorithm.Chromosome;
import genetic_algorithm.GA;

import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Random;

//implementation of genetic algorithm for the monkey problem 
public class GA_monkey_alg implements GA
{
	//initializing variables
	int POPULATION_SIZE=50;
	int TEXT_SIZE=200;
	int MUTATION_RATE=500;
	int NUM_OF_GENERATIONS=6000;
	int CROSSOVER_RATE=95;
	ArrayList<Character> alphabet;


	//methods that runs the algorithm
	public void run_alg(String hamlet_file, ArrayList<Character> alphabet) throws IOException
	{
		//updating alphabet
		this.alphabet=alphabet;
		MonkeyChromosome.hamlet_file = hamlet_file;
		Random r=new Random();

		//file that writes data about best and avg fitness to draw graph later
		FileWriter fw=new FileWriter("monkey_graph2.csv");
		fw.write("num_generation,best_fitness,avg_fitness");
		fw.write('\n');
		
		//getting initial population
		ArrayList<Chromosome> population=initiate_population(POPULATION_SIZE);
		
		int count=0;
		ArrayList<Chromosome> selected;
		ArrayList<Chromosome> children;
		
		boolean foundSolution=false;
		
		//running maximum NUM_OF_GENERATIONS generations
		while(count<NUM_OF_GENERATIONS)
		{

			//finding best chromosome
			Chromosome best=getMaxAndRemoveWorst(population);
			int best_fitness=(int)best.evaluateFitness();
			
			//found the perfect solution
			if(best_fitness==TEXT_SIZE)
			{
				foundSolution=true;
				break;
			}
			
			//writing data to the file
			fw.write(count+","+best_fitness);
			population.remove(best);
			
			//finding second best chromosome
			Chromosome second_best=getMaxAndRemoveWorst(population);
			population.add(best);
			
			//calculating average fitness
			double avg=calcAvgFitness(population);
			
			fw.write(","+avg);
			fw.write('\n');
		
			//selecting parents for crossover
			selected=selection(population,avg);
			
			population.clear();
			
			//list of selected chromosomes we didn't crossover yet
			ArrayList<Integer> indexes_not_chosen_yet=new ArrayList<Integer>();
			
			// all of the selected chromosomes haven't been crossovered yet
			for(int i=0;i<POPULATION_SIZE-2;i++)
				indexes_not_chosen_yet.add(i);
			
			int index1,index2;
			for(int i=0;i<POPULATION_SIZE-2;i+=2)
			{
				//choosing index of first chromosome to crossover
				index1=r.nextInt(indexes_not_chosen_yet.size());
				int first_index=indexes_not_chosen_yet.get(index1);
				indexes_not_chosen_yet.remove(index1);
				
				//choosing index of second chromosome to crossover
				index2=r.nextInt(indexes_not_chosen_yet.size());
				int second_index=indexes_not_chosen_yet.get(index2);
				indexes_not_chosen_yet.remove(index2);
				
				//crossover of the chosen parents
				children=crossover(selected.get(second_index),selected.get(first_index));
				population.addAll(children);
			}

			//adding best and second best chromosomes to next generation (top 2 elitism)
			population.add(best);
			population.add(second_best);
			
			count++;
		}

		String best_sol="";
		int max_fitness=0;
		
		//finding best solution in the final generation
		for(Chromosome chr: population)
		{
			if(chr.evaluateFitness()>max_fitness)
			{
				max_fitness=(int) chr.evaluateFitness();
				best_sol=chr.toString();
			}

		}

		//printing best solution and its fitness
		System.out.println("The best solution is:"+best_sol);
		System.out.println(" and the max fit: " + max_fitness);
		
		if(!foundSolution)
			System.out.println("no solution found");
		else
			System.out.println("found solution in "+count+" iterations");

		fw.close();
		

	}
	
	
	//function that finds best chromosome and removes worst
	private Chromosome getMaxAndRemoveWorst(ArrayList<Chromosome> population)
	{
		int max_fitness=-1;
		int max_index=-1;
		
		int min_fitness=201;
		int min_index=-1;
		for(int i=0;i<population.size();i++)
		{
			//found new maximum
			if(population.get(i).evaluateFitness()>max_fitness)
			{
				max_fitness=(int) population.get(i).evaluateFitness();
				max_index=i;
			}
			
			//found new minimum
			if(population.get(i).evaluateFitness()<min_fitness)
			{
				min_fitness=(int) population.get(i).evaluateFitness();
				min_index=i;
			}
		}
		
		Chromosome best=population.get(max_index);
		//removing worst
		population.remove(min_index);
		return best;
	}
	
	//initiate population with given size
	@Override
	public ArrayList<Chromosome> initiate_population(int size) 
	{
		Random r = new Random();
		ArrayList<Chromosome> population=new ArrayList<Chromosome>(size);
		String text;
		int index;

		//initializing size random chromosomes
		for(int i=0;i<size;i++)
		{
			text="";

			//choosing each letter in random
			for(int j=0;j<TEXT_SIZE;j++)
			{
				index=r.nextInt(alphabet.size());
				text+=alphabet.get(index);
			}

			//adding the new chromosome
			population.add(new MonkeyChromosome(text));
		}

		return population;
	}

	//selecting N chromosomes from population using the SUS method
	@Override
	public ArrayList<Chromosome> selection(ArrayList<Chromosome> population,double avg) 
	{
		int N=population.size();
		int T = calcSumExpVal(population,avg);
	
		Random r=new Random();
		double num=r.nextInt(T);
		double sum = 0.0;
		int j;
		ArrayList<Chromosome> selected=new ArrayList<Chromosome>();
		
		//selecting N chromosomes
		for(int i=0;i<N;i++)
		{

			//running through the chromosomes until the sum is bigger than num
			for(j=0;j<N;j++)
			{
				sum+=ExpVal(j,population,avg);
				if(sum>num)
				{	
					//adding the chromosome we found
					selected.add(population.get(j));
					
					//we want to find next chromosomes, which is located at T/N from the previous
					num = (num+((double)T/N)) % T;
					sum = 0.0;
					break;
				}
			} 
		}
		return selected;
		
		/*
		double avg=calcAvgFitness(population);
		int N=population.size();
		Random r=new Random();
		ArrayList<Chromosome> selected=new ArrayList<Chromosome>();
		for(int i=0;i<N;i++)
		{
			int num=r.nextInt(N);
			
			double sum=0.0;
			int j;
			for(j=0;j<N;j++)
			{
				sum+=ExpVal(j,population,avg);
				if(sum>num)
					break;
			} 
			
			//System.out.println("sum "+sum);
			//System.out.println("num "+num);
			selected.add(population.get(j));
		}
		return selected;
		*/
	}

	//calculating sum of expected values of the population
	private int calcSumExpVal(ArrayList<Chromosome> population,double avg) 
	{
		double sum=0.0;
		for(int i=0;i<population.size();i++)
		{
			sum+=ExpVal(i, population, avg);
		}
		return (int)sum;
	}

	//calculating expected value using sigma scaling
	private double ExpVal(int i,ArrayList<Chromosome> population,double avg)
	{
		double sdev=CalcStandardDevitation(population, avg);
		double temp;
		
		if(sdev!=0)
		{
			//calculating according to sigma scaling
			temp = 1+((population.get(i).evaluateFitness()-avg)/2*sdev);
			if(temp >= 0)
			{
				return temp;
			}
			
			//if it's negative returning a small number
			else
			{
				return 0.00001;
			}
		}
		else
			return 1;
	}
	
	//calculate standard deviation of the population fitness
	private double CalcStandardDevitation(ArrayList<Chromosome> population, double avg)
	{
		int sum=0;
		
		//summing squares of differences
		for(Chromosome chrm:population)
		{
			sum+=Math.pow(chrm.evaluateFitness()-avg, 2);
		}
		return Math.sqrt(sum/population.size());
	}

	//calculating average of fitness
	private double calcAvgFitness(ArrayList<Chromosome> population){

		int sum=0;

		//summing all fitnesses
		for(Chromosome chrm:population)
		{
			sum+=chrm.evaluateFitness();
		}

		return ((double)sum)/population.size();
	}


	//implementation of universal crossover
	@Override
	public ArrayList<Chromosome> crossover(Chromosome parent1,
			Chromosome parent2){

		Random rnd=new Random();
		ArrayList<Chromosome> children=new ArrayList<Chromosome>();

		int n=rnd.nextInt(100);
		
		//we chose not to crossover
		if(n>=CROSSOVER_RATE)
		{
			//return parents withput change
			children.add(parent1);
			children.add(parent2);
			return children;
		}
		
		String child1 = "", child2 = "";
		int num;

		//creating two new children
		for (int i = 0; i < TEXT_SIZE; i++) 
		{
			//tossing a coin
			num = rnd.nextInt(2);
			
			//taking char for first child from first parent and for second child from second parent
			if(num==0)
			{
				child1+=parent1.toString().charAt(i);
				child2+=parent2.toString().charAt(i);
			}
			//taking char for first child from second parent and for second child from first parent
			else
			{
				child1+=parent2.toString().charAt(i);
				child2+=parent1.toString().charAt(i);
			}
		}

		//adding children after mutating
		children.add(mutation(new MonkeyChromosome(child1)));
		children.add(mutation(new MonkeyChromosome(child2)));


		return children;
	}

	//altering each character at certain probability
	@Override
	public Chromosome mutation(Chromosome chrm)
	{

		Random r=new Random();
		String new_text="";
		int index,num;
		
		//for each character
		for(int i=0;i<TEXT_SIZE;i++)
		{
			num=r.nextInt(MUTATION_RATE);
			
			//at probability 1/MUTATION_RATE
			if(num==0)
			{
				//choosing another character at random
				index=r.nextInt(alphabet.size());
				new_text+=alphabet.get(index);
			}
			else
				new_text+=chrm.toString().charAt(i);
		}
		
		return (new MonkeyChromosome(new_text));
	}

}
